#include"shortest_path.h"

using namespace std;

void dfs(int &cnt, int u, string path, int start, vector<int> last[], char *data)
{
    if (u == start) {
        if (!cnt) printf("Shortest path:\n");
        printf("No.%d:%c->", ++cnt, data[start]);
        for (int i = path.size() - 1; i >= 0; i--) {
            if (i == path.size() - 1) printf("%c", path[i]);
            else printf("->%c", path[i]);
        }
        printf("\n");
        return;
    }
    for (auto item : last[u]) {
        dfs(cnt, item, path + data[u], start, last, data);
    }
}

void dijsktra(int n, int g[][N], int start, int end, char data[], vector<int> last[])
{
    bool has_shortest_path = false;
    int dist[N] = {0};
    memset(dist, 0x3f, sizeof dist);
    bool st[N] = {0};
    dist[start] = 0;

    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;
        for (int j = 1; j <= n; j++) {
            if (dist[j] > dist[t] + g[t][j]) {
                dist[j] = dist[t] + g[t][j];
                last[j].clear();
                last[j].push_back(t);
            } else if (dist[j] == dist[t] + g[t][j]) {
                last[j].push_back(t);
            }
        }
    }
    if (dist[end] != 0x3f3f3f3f)
        has_shortest_path = true;

    if (!has_shortest_path)
        printf("There is no shortest path from %c to %c\n", data[start], data[end]);
    else {
        int cnt = 0;
        dfs(cnt, end, "", start, last, data);
    }
}